The invention relates to a method for the real-time analysis of a system, in particular of a technical system.
With a large number of technical systems, such as embedded real-time systems or embedded computer systems, it is necessary that the system processes tasks within a specified time interval which is also designated with a time limit or deadline, i.e. that it is real-time capable. Tasks which are to be processed by the system are collectively referred to below as a “task system”.
Real-time analysis can be used for automating the development of real-time systems. Furthermore, it is possible to conduct a real-time analysis while the task system is being processed by the system. If during the processing it is determined that specified real-time conditions cannot be maintained by the system, measures can be introduced, for example, for a limited but essentially secure processing of the task system. Measures of this type can for example consist of transferring individual tasks onto other systems or system components in order to process them. It is also possible to postpone the processing of individual tasks in order to give preference to other tasks.
Methods for real-time analysis can be divided into sufficient and necessary methods. With a necessary method, a system can consistently be classified without error for a specified task system. By contrast, with a sufficient method, it can be the case that the system is erroneously specified as being not real-time capable for a specified task system, even though the system would actually be in a position to process the task system while maintaining the specified real-time conditions.
A necessary method for the real-time analysis for a processor of a computer is known from S. Baruah, A. Mok, L. Rosier: “Preemtively Scheduling Hard-Real-Time Sporadic Tasks on One Processor” in Proceedings of the Real-Time Systems Symposium, 182-190, 1990. With the method, a maximum test interval, i.e. a maximum time interval is initially calculated for a specified task system. Then a time interval which is inserted in the test interval is selected according to a specified criterion and the computing time required for the tasks to be processed within the time interval is computed by the processor. Then the computing time is compared with the length of the time interval. A task system is not classified as being processable in real-time when the computing time is greater than the length of the time interval. If the system is real-time capable for the selected time interval, a further time interval which is inserted in the test interval is checked. The procedure is continued either until it is determined that the system is not real-time capable, or until all time intervals which fulfil the criterion have been checked. With the method, only those time intervals need to be checked which lie within the test interval. However, it can be the case that many time intervals are checked unnecessarily, as a result of which the run time for the method is prolonged unnecessarily.
A method is known from J. A. Stankovic, M. Spuri, K. Ramamritham, G. C. Buttazzo: “Deadline Scheduling for Real-Time Systems EDF and Related Algorithms”, in Kluwer Academic Publishers, Boston/Dodrecht/London, 1998, p. 42-50, in which the number of time intervals to be checked can be reduced as compared with the method according to Baruah et. al. Only those time intervals are taken into account in which the computing time of the system can change. A disadvantage of this method is that its run time is dependent not on the size of the task system, but also on the relationship of parameters of the tasks such as the period, deadline or execution time. It is known from Karsten Albers, Frank Slomka: “An Event System driven Approximation for the Analysis of Real-Time Systems” in IEEE Proceedings of the 16th Euromicro Conference on Real-Time Systems 2004 (ECRTS'04), Catania, Italy, p. 187-195, that a real-time analysis for a task system which contains both tasks with small and large periods requires a long run time with the method according to Stankovich et. al. Furthermore, with task systems with a high degree of work load of the system, very many time intervals must be checked. This results in a long run time for the method.
A sufficient effectual method for real-time analysis is known from M. Devi: “An Improved Schedulability Test for Uniprocessor Periodic Task Systems”, in IEEE Proceedings of the 15th Euromicro Conference on Real-Time Systems, 2003. This method is a further development of the method described above. The run time for the method is essentially dependent only on the size of the task system. A method of this type is also known as a “method with polynominal complexity”. With the method according to Devi, it can be the case, however, that a system which is in fact real-time capable for a task system is not recognised as such, and is erroneously classified. This is the case with task systems which enable an optimum utilisation of the system, for example.
A further method for real-time analysis is known from S. Chakraborty, S. Künzli, L. Thiele: “Approximate Schedulability Analysis”, 23rd IEEE Real-Time Systems Symposium (RTSS), IEEE Press, 159-168, 2002. The method is an approximation method in which a maximum error can be firmly specified. In order to check the real-time capability, a firmly specified number of time intervals are checked. The maximum number of errors depends on the number of time intervals. The time intervals can be maintained by a minimum time interval being successively enlarged, in each case by a specified amount. For each time interval, a precise calculation is made of the computing time required by the system for processing the tasks to be processed within the time interval. The computing time is compared with a system capacity which is made available to the system within the next smallest time interval in order to process the tasks. On the basis of the comparison, it is determined whether the system is real-time capable. A disadvantage of the method is that the comparison leads to an error which can no longer be fully compensated by a large number of time intervals. Many systems are erroneously classified as being not real-time capable for a specified task system. A further disadvantage is that when a small maximum error is selected, the run time of the method can be longer than that of a precise method. With the method described above which is known according to the prior art, it is necessary to determine a precision or an error in the method before the method is implemented. A selected error which is too large for a specified task system can lead to the system being erroneously classified as being not real-time capable. When a selected error is too small, this leads to a large degree of time and effort and too long run times.